Ban đầu Fredericia được thiết lập như 1 công sự phòng thủ. Sau kinh nghiệm của cuộc chiến tranh 30 năm (1618-48) mà Đan Mạch tham gia từ năm 1625-29, vua Christian IV thấy cần phải xây dựng 1 pháo đài vững mạnh ở Jutland để phòng thủ, cùng với kế hoạch lập 1 thành phố lớn ở Jutland gọi là Jyllands By. Sau khi không chọn địa điểm ở "Houens Odde", thì "Lyngs Odde" được chọn. Người ta thiết lập 1 trại quân với bờ lũy bao quanh theo dạng hình bán nguyệt từ bờ biển trở vào. Tuy nhiên, trong cuộc chiến tranh với Thụy Điển, quân của tướng Thụy Điển Torstenson đã dễ dàng vượt qua công sự này. Do đó vua Frederik III - theo đề nghị của thống chế Anders Bille - đã lập công sự phòng thủ ở vùng hoang Bers odde. Ngày 15.12.1650, nhà vua ký giấy lập thành phố và hào lũy phòng thủ cùng cấp đặc quyền cho thành phố. Năm 1651 đặt tên thành phố là Frederiksodde theo tên nhà vua. Ngày 22.4.1664 thành phố mang tên latin hóa Fredericia như hiện nay.

Trong cuộc chiến tranh 3 năm giữa Đan Mạch với quân nổi dậy vùng Schleswig-Holstein với sự hỗ trợ của quân Phổ, Fredericia được chọn là thành phố quân trấn của quân Đan Mạch. Mùa hè năm 1849, quân thù bao vây Fredericia. Họ bố trí các súng đại bác quanh thành phố để chặn việc tiếp tế và bổ sung quân cho thành phố. Tuy nhiên quân Đan Mạch đã đi đường biển vào thành phố. Đêm 6.7.1849, quân Đan Mạch tấn công các vị trí của quân địch đang bao vây. Sau cuộc chiến khốc liệt, quân Đan Mạch đã phá tan hầu hết vị trí của quân địch. 4 ngày sau, 2 bên đã ký hiệp định đình chiến, kết thúc cuộc chiến. Ngày nay, hàng năm vào ngày 6.7 Fredericia đều tổ chức lễ mừng chiến thắng này.